package acwing.算法进阶打卡;

import java.util.Scanner;

/**
 * @author： li
 * @date： 2022-03-13 15:56
 * @version 1.0
 */
/*
* 从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式
输入一个整数 n。

输出格式
每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围
1≤n≤15*/
public class 递归实现指数型枚举 {
    static int n;
    //用二进制状态压缩,也就是用二进制上的位来记录数有没有被用过。
// u是当前枚举到的数，state是二进制数记录哪些数被选
    static void dfs(int u ,int state){
        if( u == n){
            for(int i = 0; i< n; i++)
                //判断第i位是不是1，如果是1就代表被选，输出
                if(((state >> i )& 1)==1)
                    //第几位就代表输出几，只不过不是从0开始，而是从1开始
                    System.out.print((i+1)+" ");
            System.out.println(" ");
            return;
        }
        // 不用这个数，第u位不动
        dfs(u + 1, state);
        // 用这个数，把第u位变成1
        // 运算优先级： 左移高于位运算|
        dfs(u + 1, state | 1 << u);


    }
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        n = in.nextInt();
    /*
    回顾一下dfs参数的含义：
        - u是当前枚举到的数，
        -state是二进制数记录哪些数被选
    则 dfs(0, 0)表示：当前枚举到0，没有数被选

    */
            dfs(0, 0);

        in.close();
    }
}
